This application is based on an application No. H11-15592 filed in Japan, the content of which is hereby incorporated by reference.
1. Field of the Invention
The present invention relates to elliptic curve arithmetic operation techniques and elliptic curve application techniques.
2. Description of the Prior Art
In recent years, the use of elliptic curves is becoming popular in the encrypted communications technology. Cryptosystems that employ elliptic curves rely for their security on the difficulty of solving a discrete logarithm problem.
Representative examples of the discrete logarithm problem are problems based on finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag (1987).
The elliptic curve discrete logarithm problem is the following.
Let E(GF(p)) be an elliptic curve defined over a finite field GF(p), with a point G on the elliptic curve E, given when the order of E is divisible by a large prime, being set as a base point. Here, xe2x80x9cthe order of the elliptic curvexe2x80x9d means the number of points on the elliptic curve whose coordinates are in GF(p). This being so, the problem is to find an integer x such that
Y=xG
where Y is a given point on E, if such an integer x exists.
Here, p is a prime and GF(p) contains p elements.
Given that various cryptanalysis attacks against elliptic curve discrete logarithm problems have been devised over the years, it is of great importance to construct a secure elliptic curve to strengthen the elliptic curve cryptosystem against these attacks.
In this specification, xe2x80x9cconstructing an elliptic curvexe2x80x9d roughly means to determine the parameters a and b of an elliptic curve which is given by an equation
y{circumflex over ( )}2=x{circumflex over ( )}3+ax+b
where the sign {circumflex over ( )} represents a repeated multiplication, such as x{circumflex over ( )}3=xxc3x97xxc3x97x.
To be secure against all existing cryptanalysis attacks, an elliptic curve over the finite field GF(p) must satisfy the conditions:
(a) the order of the elliptic curve is not equal to any of pxe2x88x921, p, and p+1; and
(b) the order of the elliptic curve has a large prime factor.
In other words, checking the order of the elliptic curve allows the security of the elliptic curve to be assessed.
According to T. Okamoto and K. Ohta Encryption, Zero Knowledge Proof, and Number Theory, Kyoritsu (1995), pp.155xcx9c156, when the above conditions are satisfied, computation time required to solve the elliptic curve discrete logarithm problem is exponential time in the largest prime factor of the elliptic curve order.
There are mainly two elliptic curve construction methods that are:
{circle around (1)} elliptic curve construction using the CM (Complex Multiplication) method; and
{circle around (2)} elliptic curve construction using an order computation algorithm.
Although {circle around (1)} can construct an elliptic curve easily, it cannot choose an elliptic curve at random. For details of this method, see A. Miyaji xe2x80x9cOn Ordinary Elliptic Curve Cryptosystemsxe2x80x9d ASIACRYPT""91, Springer-Verlag (1991), pp.460xcx9c469. Meanwhile, {circle around (2)} can construct a random elliptic curve, though it takes considerable time to do so.
The following introduces the method of constructing an elliptic curve using an algorithm to compute the order of the elliptic curve, with reference to FIG. 1. For details on this method, see N. Koblitz xe2x80x9cElliptic Curve Implementation of Zero-Knowledge Blobsxe2x80x9d J. Cryptology, vol.4, no.3 (1991), pp.207xcx9c213.
First, a random number is generated (S901), and parameters which define the elliptic curve are generated using the random number (S902). Next, the order of the elliptic curve is computed using the generated parameters (S903). The computed order is checked whether it satisfies one or more predetermined conditions for secure elliptic curves, to assess the security of the elliptic curve (S904). If and only if the order satisfies the conditions, the generated elliptic curve parameters are outputted. If the order does not satisfy the conditions, the procedure returns to step S901 to repeat the random number generation, the parameter generation, the order computation, and the security judgement, until an elliptic curve whose order satisfies the conditions in step S904 is found.
This method which employs an order computation algorithm requires long computation time. Especially, it takes much time to compute the order of the elliptic curve.
One example of algorithms used to compute orders of elliptic curves is an algorithm proposed by Schoof. This algorithm is a polynomial time algorithm. The polynomial time algorithm referred to here is an algorithm whose computation time is polynomial time. The computation time of Schoof""s algorithm per se is not practical.
Atkin and Elkies have proposed several improvements of Schoof""s algorithm and so have designed the SEA (Schoof-Elkies-Atkin) algorithm.
This algorithm is detailed in R. Lercier and F. Morain xe2x80x9cCounting the Number of Points on Elliptic Curves over Finite Fields: Strategies and Performancesxe2x80x9d EUROCRYPT""95, Springer-Verlag (1995), pp.79xcx9c94.
The SEA algorithm computes t mod L{circumflex over ( )}n (n=1, 2, 3, . . . ). This can be done by calculating an eigenvalue of a map called the Frobenius map. More specifically, k is found from an equation
(xcex1{circumflex over ( )}p,xcex2{circumflex over ( )}p)=k(xcex1,xcex2)
where (xcex1,xcex2) is an L-division point on an elliptic curve E and k(xcex1,xcex2) is a point on E after exponentiating the point (xcex1,xcex2) by k. This is carried out through computation on the elliptic curve E on a residue class ring of polynomials in variable xcex1 and xcex2 with elements of GF(p) as coefficients, the moduli of the ring being polynomials xcex2{circumflex over ( )}2xe2x88x92f(xcex1) and h(xcex1). Computational complexity of the inversion of a polynomial is greater than computational complexity of the multiplication of a polynomial, so that a 3-tuple coordinate is used in this computation. Here, projective coordinate is employed as the 3-tuple coordinate, as the projective coordinate has been conventionally used for elliptic curves over finite fields. Conventional projective coordinate is described in Miyaji, Ono and Cohen xe2x80x9cEfficient Elliptic Curve Exponentiationxe2x80x9d Advances in Cryptology-Proceedings of ICICS""97, Lecture Notes in Computer Science, Springer-Verlag (1997), pp.282-290.
Exponentiating the point (xcex1,xcex2) on the elliptic curve E by k is done by splitting the exponentiation into additions and doublings and performing the additions and the doublings in the following way.
Suppose (xcex1,xcex2) is transformed to (xcex1:xcex2:1), and (xcex1:xcex2:1) is interpreted as (X(xcex1):xcex2xc3x97Y(xcex1):Z(xcex1) (where X(xcex1)=xcex1 and Y(xcex1)=Z(xcex1)=1).
Note here that xe2x80x9c( , )xe2x80x9d and xe2x80x9c( : : )xe2x80x9d represent affine coordinates and projective coordinates, respectively.
Assume
P1=(X1(xcex1):xcex2xc3x97Y1(xcex1):Z1(xcex1))
P2=(X2(xcex1):xcex2xc3x97Y2(xcex1):Z2(xcex1))
P3=P1+P2=(X3(xcex1):xcex2xc3x97Y3(xcex1):Z3(xcex1))
In this specification, the operators xc3x97 and * in an addition formula or a doubling formula both denote a multiplication. In the addition formula or the doubling formula, a multiplication which appears for the first time in the formula is expressed by the operator *, whereas a multiplication which has already appeared is expressed by the operator xc3x97. The number of multiplications in the addition or doubling formula can be obtained by counting the number of operators * in the formula.
(1) Addition Formula
When P1xe2x89xa0xc2x1P2, addition is required, the formula of which is
X3=v*A
Y3=u*(v{circumflex over ( )}2xc3x97X1xc3x97Z2xe2x88x92A)xe2x88x92v{circumflex over ( )}3*(Y1xc3x97Z2)
Z3=v{circumflex over ( )}3*(Z1xc3x97Z2)
where       u    =                  Y2        *        Z1            -              Y1        *        Z2                  v    =                  X2        *        Z1            -              X1        *        Z2                                          A          =                                    u              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2              xc3x97                              f                ⁡                                  (                  α                  )                                            xc3x97              Z1              xc3x97              Z2                        -                          v              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              3                        -                          2              xc3x97              v              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2              xc3x97              X1              xc3x97              Z2                                                                    =                                                    (                                                      (                                          u                      *                      u                                        )                                    *                                      f                    ⁡                                          (                      α                      )                                                                      )                            *                              (                                  Z1                  *                  Z2                                )                                      -                                          (                                  v                  *                  v                                )                            *              v                        -                          2              xc3x97              v              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2              *                              (                                  X1                  xc3x97                  Z2                                )                                                        
and
f(x)=x{circumflex over ( )}3+ax+b
It is to be noted that, although X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3, u, v, and A are polynomials in the variable xcex1 and therefore should be written like X1(xcex1), Y1(xcex1), and Z1(xcex1) to be precise, (xcex1) has been omitted here for convenience in writing.
(2) Doubling Formula
When P1=P2, doubling is required, the formula of which is       X3    =          2      xc3x97      h      *              (                  s          xc3x97                      f            ⁡                          (              α              )                                      )                                          Y3          =                                    w              xc3x97                              (                                                      4                    xc3x97                    B                                    -                  h                                )                                      -                          8              xc3x97              Y1              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2              xc3x97              s              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2              xc3x97                              f                ⁡                                  (                  α                  )                                            ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2                                                                    =                                    w              *                              (                                                      4                    xc3x97                    B                                    -                  h                                )                                      -                          8              xc3x97                              (                                  Y1                  xc3x97                  s                  xc3x97                                      f                    ⁡                                          (                      α                      )                                                                      )                            *                              (                                  Y1                  xc3x97                  s                  xc3x97                                      f                    ⁡                                          (                      α                      )                                                                      )                                                                                      Z3          =                      8            xc3x97            s            ⁢                          xe2x80x83                        ⁢                                          xe2x80x83                            ^                        ⁢            3            xc3x97                          f              ⁡                              (                α                )                                      ⁢                          xe2x80x83                        ⁢                                          xe2x80x83                            ^                        ⁢            2                                                        =                      8            xc3x97            s            *                          (                              s                xc3x97                                  f                  ⁡                                      (                    α                    )                                                              )                        *                          (                              s                xc3x97                                  f                  ⁡                                      (                    α                    )                                                              )                                          
where                               w          =                                    a              xc3x97              Z1              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2                        +                          3              xc3x97              X1              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2                                                                    =                                    a              xc3x97                              (                                  Z1                  *                  Z1                                )                                      +                          3              xc3x97                              (                                  X1                  *                  X1                                )                                                              s    =          Y1      *      Z1            B    =          X1      *              (                  Y1          *                      (                          s              *                              f                ⁡                                  (                  α                  )                                                      )                          )                                          h          =                                    w              ⁢                              xe2x80x83                            ⁢                                                xe2x80x83                                ^                            ⁢              2                        -                          8              xc3x97              B                                                                    =                                    w              *              w                        -                          8              xc3x97              B                                          
and
f(x)=x{circumflex over ( )}3+ax+b
As with the addition formula, though X1, Y1, Z1, X3, Y3, Z3, w, s, B, and h are polynomials in the variable xcex1, (xcex1) is omitted for convenience in writing.
The number of multiplications is 15 in the addition formula and 12 in the doubling formula, as can be seen from the number of operators * in each of the formulas. When computational complexity of a polynomial multiplication is measured as 1xc3x97PMul, the computational complexity of the addition is 15xc3x97PMul and the computational complexity of the doubling is 12xc3x97PMul.
In counting the number of multiplications, computational complexity of multiplying a constant and a polynomial, such as axc3x97(Z1{circumflex over ( )}2) or 3xc3x97(X1{circumflex over ( )}2), is smaller than computational complexity of multiplying a polynomial and a polynomial, so that such a multiplication is ignored in the counting. Likewise, a multiplication which has once appeared does not have to be calculated again because the previous multiplication result can be used, so that such a multiplication is ignored in the counting.
A method of constructing elliptic curves using -the SEA algorithm is proposed in pp. 379xcx9c392 in R. Lercier xe2x80x9cFinding Good Random Elliptic Curves for Cryptosystems Defined over F(2{circumflex over ( )}n)xe2x80x9d Advances in Cryptology-Proceedings of EUROCRYPT""97, Lecture Notes in Computer Science, 1233, Springer-Verlag (1997) (hereinafter referred to as xe2x80x9cdocument 1xe2x80x9d). In this method the predetermined conditions used in the elliptic curve construction of prior art example 1 are defined as xe2x80x9cthe order of the elliptic curve is a primexe2x80x9d.
Lercier""s elliptic curve construction method which employs the SEA algorithm is described below with reference to FIGS. 2 and 3.
Let p be a prime which is an input value. Also, let E be an elliptic curve over a finite field GF(p) and Exe2x80x2 be the quadratic twist of E. Then there is the relationship that, if the order of E is p+1xe2x88x92t, the order of Exe2x80x2 is p+1+t.
First, an element u of the finite field GF(p) is chosen at random (S931), and parameters of the elliptic curve E are determined based on the element u (S932). Then, flags flag#ell and flag#twist are both set at an initial value 1 (S933).
Next, the order of E and the order of Exe2x80x2 are calculated according to the SEA algorithm (S934).
If the order of E is divisible by L (S935), flag#ell is changed to 0 (S936), whereas if the order of Exe2x80x2 is divisible by L (S937), flag#twist is changed to 0 (S938). When flag#ell=0 and flag#twist=0 (S940), the procedure returns to step S931. Otherwise, the procedure proceeds to step S941.
When flag#ell=1 (S941), it is judged whether the order of E is prime (S942). If the order of E is prime, the procedure proceeds to step S945. If the order of E is not prime, it is judged whether flag#twist=1 (S943). When flag#twistxe2x89xa01, the procedure returns to step S931. When flag#twist=1, it is judged whether the order of Exe2x80x2 is prime (S944). If the order of Exe2x80x2 is not prime, the procedure returns to step S931. If the order of Exe2x80x2 is prime, the procedure proceeds to step S945.
It is judged in step S945 whether the order of E is equal to p. If the order is equal to p, the procedure returns to step S931. If the order is not equal to p, the parameters of the elliptic curve E are outputted (S946).
In Lercier""s elliptic curve construction, step S933 is used to accelerate computation, thereby reducing computation time needed for the SEA algorithm. Nevertheless, since in step S932 the parameters of the elliptic curve E are determined without consideration given to the possibility that the order of the elliptic curve E is not prime, the order computation according to the SEA algorithm in step S934 may have to be repeated again and again. This causes an increase in overall computational complexity.
Thus, despite the fact that Schoof""s order computation algorithm in elliptic curve construction has been modified as the SEA algorithm and improvements to reduce computational complexity of the SEA algorithm have been proposed by Lercier, there still remains the demand to further reduce computational complexity for elliptic curves.
The first object of the invention is to provide an elliptic curve arithmetic operation device that can compute points on an elliptic curve with small computational complexity.
The second object of the invention is to provide an elliptic curve order computation device that can compute an order of an elliptic curve with small computational complexity.
The third object of the invention is to provide an elliptic curve construction device that can construct a highly secure elliptic curve with small computational complexity.
The fourth object of the invention is to provide an elliptic curve application device that uses a highly secure elliptic curve constructed with small computational complexity.
The first object can be fulfilled by an elliptic curve arithmetic operation device for performing one of an addition and a doubling on an elliptic curve E: y{circumflex over ( )}2=f(x) on a residue class ring of polynomials in two variables xcex1 and xcex2, moduli of the residue class ring being polynomials xcex2{circumflex over ( )}2xe2x88x92f(xcex1) and h(xcex1), where f(xcex1)=xcex1{circumflex over ( )}3+axcex1+b, a and b are constants, and h(xcex1) is a polynomial in the variable xcex1, the elliptic curve arithmetic operation device including: an acquiring unit for acquiring affine coordinates of at least one point on the elliptic curve E and operation information indicating one of the addition and the doubling, from an external source; a transforming unit for performing a coordinate transformation on the acquired affine coordinates to generate Jacobian coordinates, the coordinate transformation being transforming affine coordinates (xcfx86(xcex1),xcex2xc3x97"PHgr"(xcex1)) of a given point on the elliptic curve E using polynomials
X(xcex1)=f(xcex1)xc3x97xcfx86(xcex1)
Y(xcex1)=f(xcex1){circumflex over ( )}2xc3x97"PHgr"(xcex1)
Z(xcex1)=1
into Jacobian coordinates (X(xcex1):Y(xcex1):xcex2xc3x97Z(xcex1)), xcfx86(xcex1) and "PHgr"(xcex1) being polynomials; and an operating unit for performing one of the addition and the doubling indicated by the acquired operation information, on the generated Jacobian coordinates to obtain Jacobian coordinates of a point on the elliptic curve E.
Here, the acquiring unit may in a first case acquire affine coordinates of two different points on the elliptic curve E and operation information indicating the addition and in a second case acquire affine coordinates of a single point on the elliptic curve E and operation information indicating the doubling, wherein the transforming unit in the first case performs the coordinate transformation on the acquired affine coordinates of the two different points to generate Jacobian coordinates of the two different points and in the second case performs the coordinate transformation on the acquired affine coordinates of the single point to generate Jacobian coordinates of the single point, and the operating unit in the first case performs the addition indicated by the acquired operation information on the generated Jacobian coordinates of the two different points to obtain the Jacobian coordinates of the point on the elliptic curve E and in the second case performs the doubling indicated by the acquired operation information on the generated Jacobian coordinates of the single point to obtain the Jacobian coordinates of the point on the elliptic curve E.
Here, the acquiring unit may in the first case acquire affine coordinates
(X1(xcex1),xcex2xc3x97Y1(xcex1))
(X2(xcex1),xcex2xc3x97Y2(xcex1))
of the two different points on the elliptic curve E and the operation information indicating the addition and in the second case acquire affine coordinates
(X1(xcex1),xcex2xc3x97Y1(xcex1))
of the single point on the elliptic curve E and the operation information indicating the doubling, wherein the transforming unit in the first case performs the coordinate transformation on the acquired affine coordinates of the two different points to generate Jacobian coordinates
(X1(xcex1):Y1(xcex1):xcex2xc3x97Z1(xcex1))
(X2(xcex1):Y2(xcex1):xcex2xc3x97Z2(xcex1))
of the two different points and in the second case performs the coordinate transformation on the acquired affine coordinates of the single point to generate Jacobian coordinates
(X1(xcex1):Y1(xcex1):xcex2xc3x97Z1(xcex1))
of the single point, and the operating unit in the first case computes
U1(xcex1)=X1(xcex1)xc3x97Z2(xcex1){circumflex over ( )}2
U2(xcex1)=X2(xcex1)xc3x97Z1(xcex1){circumflex over ( )}2
S1(xcex1)=Y1(xcex1)xc3x97Z2(xcex1){circumflex over ( )}3
S2(xcex1)=Y2(xcex1)xc3x97Z1(xcex1){circumflex over ( )}3
H(xcex1)=U2(xcex1)xe2x88x92U1(xcex1)
r(xcex1)=S2(xcex1)xe2x88x92S1(xcex1)
and computes
X3(xcex1)=xe2x88x92H(xcex1){circumflex over ( )}3xe2x88x922xc3x97U1(xcex1)xc3x97H(xcex1){circumflex over ( )}2+r(xcex1) {circumflex over ( )}2
Y3(xcex1)=xe2x88x92S1(xcex1)xc3x97H(xcex1){circumflex over ( )}3+r(xcex1)xc3x97(U1(xcex1)xc3x97H(xcex1){circumflex over ( )}2xe2x88x92X3(xcex1))
Z3(xcex1)=Z1(xcex1)xc3x97Z2(xcex1)xc3x97H(xcex1)
to obtain Jacobian coordinates (X3(xcex1):Y3(xcex1):xcex2xc3x97Z3(xcex1)) of the point on the elliptic curve E, and in the second case computes
S(xcex1)=4xc3x97X1(xcex1)xc3x97Y1(xcex1){circumflex over ( )}2
M(xcex1)=3xc3x97X1(xcex1){circumflex over ( )}2+a xc3x97Z1(xcex1){circumflex over ( )}4xc3x97f(xcex1){circumflex over ( )}2
T(xcex1)=xe2x88x922xc3x97S(xcex1)+M(xcex1){circumflex over ( )}2
and computes
X3(xcex1)=T(xcex1)
Y3(xcex1)=xe2x88x928xc3x97Y1(xcex1){circumflex over ( )}4+M(xcex1)xc3x97(S(xcex1)-T(xcex1))
Z3(xcex1)=2xc3x97Y1(xcex1)xc3x97Z1(xcex1)
to obtain the Jacobian coordinates (X3(xcex1):Y3(xcex1):xcex2xc3x97Z3(xcex1)) of the point on the elliptic curve E.
With the above construction, computational complexity for polynomial multiplications in the addition increases by 1xc3x97PMul and computational complexity for polynomial multiplications in the doubling decreases by 2xc3x97PMul, when compared with the prior art. Given that generally the doubling is more frequently repeated than the addition, the decrease in computational complexity of the doubling greatly contributes to a reduction in overall computational complexity in the elliptic curve arithmetic operation device.
The second object can be fulfilled by an elliptic curve order computation device for computing an order of an elliptic curve according to a Schoof-Elkies-Atkin algorithm, the elliptic curve order computation device including the above elliptic curve arithmetic operation device.
With this construction, computational complexity for polynomial multiplications in the addition increases by 1xc3x97PMul and computational complexity for polynomial multiplications in the doubling decreases by 2xc3x97PMul, when compared with the prior art. Given that generally the doubling is more frequently repeated than the addition, the decrease in computational complexity of the doubling greatly contributes to a reduction in overall computational complexity in the elliptic curve order computation device.
The third object can be fulfilled by an elliptic curve construction device for determining parameters of an elliptic curve E which is defined over a finite field GF(p) and offers a high level of security, p being a prime, the elliptic curve construction device including: a random number generating unit for generating a random number; a parameter generating unit for selecting the parameters of the elliptic curve E using the generated random number, in such a manner that a probability of a discriminant of the elliptic curve E having any square factor is lower than a predetermined threshold value; a finitude judging unit for judging whether the elliptic curve E defined by the selected parameters has any point whose order is finite on a rational number field; an order computing unit for computing an order m of the elliptic curve E when the finitude judging unit judges that the elliptic curve E does not have any point whose order is finite on the rational number field; a security judging unit for judging whether a condition that the computed order m is a prime not equal to the prime p is satisfied; a repeat controlling unit for controlling the random number generating unit, the parameter generating unit, the finitude judging unit, the order computing unit, and the security judging unit respectively to repeat random number generation, parameter selection, finitude judgement, order computation, and security judgement until the condition is satisfied; and a parameter outputting unit for outputting the selected parameters when the condition is satisfied.
With this construction, the parameter generating unit is likely to select a secure elliptic curve beforehand, so that the processes of selecting an elliptic curve and testing its security do not have to be repeated over and over again. As a result, overall computational complexity in the elliptic curve construction device is reduced.
Also, the finitude judging unit assesses the security of the elliptic curve by judging whether the elliptic curve has a point with a finite order, before the order of the elliptic curve is computed. If the elliptic curve is judged as not being secure, the elliptic curve is rejected without the order thereof being computed. Accordingly, unnecessary calculation of the order is avoided and the overall computational complexity in the elliptic curve construction device is reduced.
Here, the elliptic curve E may be expressed as y{circumflex over ( )}2=x{circumflex over ( )}3+ax+b where parameters a and b are constants, wherein the parameter generating unit selects xe2x88x923 and the random number respectively as the parameters a and b so that the probability of the discriminant of the elliptic curve E having any square factor is lower than the predetermined threshold value.
With this construction, the parameter generating unit selects the elliptic curve E: y{circumflex over ( )}2=x{circumflex over ( )}3xe2x88x923x+b which is highly secure beforehand, so that the processes of selecting an elliptic curve and testing its security do not have to be repeated over and over again. Accordingly, the overall computational complexity in the elliptic curve construction device is reduced.
Here, the finitude judging unit may, given two primes p1 and p2 beforehand where p1xe2x89xa0p2, interpret the elliptic curve E as an elliptic curve EQ on the rational number field, compute orders m1 and m2 of respective elliptic curves Ep1 and Ep2 which are produced by reducing the elliptic curve EQ modulo p1 and p2, judge whether the orders m1 and m2 are relatively prime, and, if the orders m1 and m2 are relatively prime, judge that the elliptic curve E does not have any point whose order is finite on the rational number field.
With this construction, the finitude judging unit assesses the security of the elliptic curve by judging whether the orders m1 and m2 of the elliptic curves Ep1 and Ep2 produced by reducing the elliptic curve EQ modulo pl and p2 are relatively prime, before the order of the elliptic curve is computed. If the elliptic curve is judged as not being secure, the elliptic curve is rejected without the order thereof being computed. As a result, unnecessary calculation of the order is avoided and the overall computational complexity in the elliptic curve construction device is reduced.
Here, the finitude judging unit may, given the primes p1=5 and p2=7 beforehand, compute the orders m1 and m2 of the respective elliptic curves Ep1 and Ep2 produced by reducing the elliptic curve EQ modulo p1=5 and p2=7.
With this construction, the finitude judging unit judges whether the orders m1 and m2 of the elliptic curve Ep1 and Ep2 after reducing the elliptic curve EQ modulo p1=5 and p2=7 are relatively prime. Performing the finitude judgement process in such a manner requires only the smallest computational complexity.
Here, the order computing unit may compute the order m of the elliptic curve E according to a Schoof-Elkies-Atkin algorithm and include an elliptic curve arithmetic operating unit for performing one of an addition and a doubling on the elliptic curve E: y{circumflex over ( )}2=f(x) on a residue class ring of polynomials in variables xcex1 and xcex2, moduli of the residue class ring being polynomials xcex2{circumflex over ( )}2xe2x88x92f(xcex1) and h(xcex1), where f(xcex1)=xcex1{circumflex over ( )}3+axcex1+b and h(xcex1) is a polynomial in the variable xcex1, wherein the elliptic curve arithmetic operating unit includes the above elliptic curve arithmetic operation device.
With this construction, computational complexity for polynomial multiplications in the addition increases by 1xc3x97PMul and computational complexity for polynomial multiplications in the doubling decreases by 2xc3x97PMul, when compared with the prior art. Given that normally the doubling is more frequently repeated than the addition, the decrease in computational complexity of the doubling greatly contributes to a reduction in overall computational complexity in the elliptic curve construction device.
The fourth object can be fulfilled by an elliptic curve application device that uses elliptic curves, the elliptic curve application device including an elliptic curve constructing unit for determining parameters of an elliptic curve E which is defined over a finite field GF(p) and offers a high level of security, p being a prime, wherein the elliptic curve constructing unit includes the above elliptic curve construction device.
With this construction, the elliptic curve application device delivers the same effects as the above elliptic curve construction device. Such an elliptic curve application device can achieve highly secure, fast encryption or digital signature and so has great practical applicability.